#include <iostream>
#include <vector>
#include <string>
#include <queue>
class ACautomation {
	struct Trie {
		char val = 0;
		Trie* fail = nullptr;
		std::vector<Trie*> child{std::vector<Trie*>(26, nullptr)};
		int size = 0;
	};
	Trie* root = new Trie;
private:
	void buildTrie(std::string word) {
		Trie* current = root;
		for (int i = 0; i < word.size(); ++i) {
			if (current->child[word[i] - 'a'] == nullptr) {
				current->child[word[i] - 'a'] = new Trie{word[i]};
			}
			current = current->child[word[i] - 'a'];
		}
		current->size = word.size();
	}
	void getFail() {
		std::queue<Trie*> q;
		root->fail = root;
		for (int i = 0; i < 26; ++i) {
			if (root->child[i]) {
				root->child[i]->fail = root;
				q.push(root->child[i]);
			} else {
				root->child[i] = root;
			}
		}
		while (!q.empty()) {
			Trie* current = q.front();
			q.pop();
			for (int i = 0; i < 26; ++i) {
				if (current->child[i]) {
					q.push(current->child[i]);
					current->child[i]->fail = current->fail->child[i];
				}
				else {
					current->child[i] = current->fail->child[i];
				}
			}
		}
	}
public:
	ACautomation(std::vector<std::string> words) {
		for (auto& word : words) {
			buildTrie(word);
		}
		getFail();
	}
	Trie* node = root;
	int StreamChecker(char letter) {
		node = node->child[letter - 'a'];
		return node->size;
	}
	std::string sheld(std::string s) {
		Trie* node = root;
		for (int i = 0; i < s.size(); ++i) {
			if (!isalpha(s[i])) continue;
			node = node->child[s[i] - 'a'];
			if (node->size != 0) {
				for (int j = i - node->size + 1; j <= i; ++j) s[j] = '*';
			}
		}
		return s;
	}
};
int main() {
	std::vector<std::string> words{"fuck", "bitch", "fuxk", "lust", "nipple"};
	ACautomation* ac = new ACautomation(words);
	std::string s = "suprise fucking your mother bitch!";
	//for (auto c : s) {
	//	std::cout << ac->StreamChecker(c) << " ";
	//}
	std::cout << ac->sheld(s);
	return 0;
}